package 栈.middle;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Lw中
 * @date 2021/9/12 11:00
 */
public class LuQiBa {

    // 678.有效的括号字符串

    public boolean checkValidString(String s) {
        Deque<Integer> leftStack = new LinkedList<Integer>();
        Deque<Integer> asteriskStack = new LinkedList<Integer>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                // 将左括号的下标存入左括号的栈
                leftStack.push(i);
            } else if (c == '*') {
                // 将'*'号的下标存入星号的栈
                asteriskStack.push(i);
            } else {
                if (!leftStack.isEmpty()) {
                    leftStack.pop();
                } else if (!asteriskStack.isEmpty()) {
                    asteriskStack.pop();
                } else {
                    return false;
                }
            }
        }
        while (!leftStack.isEmpty() && !asteriskStack.isEmpty()) {
            int leftIndex = leftStack.pop();
            int asteriskIndex = asteriskStack.pop();
            // 因为左括号要在星号之前所以左括号的下标要小于星号的下标，如果左括号的下标要小于星号的下标，则说明左括号无法消除
            if (leftIndex > asteriskIndex) {
                return false;
            }
        }
//        if (leftStack.size() > asteriskStack.size()) return false;
        return leftStack.isEmpty();
    }

}
